package leetCode.offer63;


/**
 * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
 * 示例 1:
 *
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
 *
 */
public class Solution1 implements Solution{

    /**
     * 解题思路，首先写一个方法其能够找到前面部分的最大差数, 类似于暴力法
     * 然后循环调用目标数组的子数组计算最大差数，取最大者
     * @param prices
     * @return
     */
    @Override
    public int maxProfit(int[] prices) {
        int result = 0;
        int length = prices.length;
        for(int i=0;i<prices.length-1;i++) {
            int[] subPrices = new int[length];
            System.arraycopy(prices,i,subPrices,0,length);
            length--;
            int subMax = maxProfitSub(subPrices);
            if(subMax>result){
                result = subMax;
            }
        }
        return result;
    }

    public int maxProfitSub(int[] prices) {
        int result = 0;
        int small = Integer.MAX_VALUE;
        int big = 0;
        int smallIndex = 0;
        int bigIndex = 1;
        for(int i=0;i<prices.length-1;i++) {
            if(prices[i]<small&&i<=bigIndex){
                small = prices[i];
                smallIndex = i;
            }
            if(prices[i+1]>big&&i+1>=smallIndex){
                big = prices[i+1];
                bigIndex = i+1;
            }
            if(result<big-small)
                result = big - small;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] param = {2,1,2,1,0,1,2};
        System.out.println(new Solution1().maxProfit(param));
    }
}
